package com.leetcode.图论;

//岛屿数量
public class lc_200 {
    public static void main(String[] args) {
        char[][] grid = {
                {'1','1','1','1','0'},
                {'1','1','0','1','0'},
                {'1','1','0','0','0'},
                {'0','0','0','0','0'}
        };
    }

    public int numIslands(char[][] grid){
        //使用count记录岛屿数量
        int count = 0;
        //对每一个格子都进行遍历
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                //如果为未遍历过的陆地,进入这一块陆地
                if(grid[i][j] == '1'){
                    //将相邻陆地全部标记
                    dfs(grid, i, j);
                    //岛屿数量+1
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 在这里: 0(海洋) 1(未遍历的陆地) 2(已遍历的陆地)
     * 这个深度遍历方法会将和这一块陆地连接的其他陆地全部进行标记
     * 新手其实可以想一想将陆地标记未海洋->(陆地沉没)只要有一块陆地,就将相邻的陆地都变为海洋
     * 进而得到这里的一块完整的岛屿
     * @param grid
     * @param i
     * @param j
     */
    public void dfs(char[][] grid,int i, int j){
        //1.边界条件: 如果超出网格边界或者不为(没遍历过的陆地) 直接return
        if(i < 0|| j < 0|| i >= grid.length || j >= grid[0].length){
            return;
        }
        if(grid[i][j] != '1'){
            return;
        }
        //2.每一层逻辑: 将已经遍历过的陆地设为2, 依次遍历这个网格的上下左右
        grid[i][j] = '2';
        //上
        dfs(grid, i - 1, j);
        //下
        dfs(grid, i + 1, j);
        //左
        dfs(grid, i, j + 1);
        //右
        dfs(grid, i, j - 1);
    }
}
